package com.jzl.leetcode.everyday.everyday876;

/**
 * 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
 *
 * 如果有两个中间结点，则返回第二个中间结点。
 *
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 *  * ListNode next;
 *  * ListNode(int x) { val = x; }
 * }
 */
public class MiddleNode {
    public ListNode middleNode(ListNode head) {
        // 创建一个节点，每次往前两步，另一个节点每次往前一步
        ListNode end = head;
        ListNode middle = head;
        if (end.next == null) {
            return middle;
        }

        while (end != null) {
            // 步进两步，如果第二步为null了，则退出。如果最后结果为null了，也正常退出。
            if ((end = end.next) != null) {
                end = end.next;
            } else {
                return middle;
            }
            middle = middle.next;
        }

        return middle;
    }
}


class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}